
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1802. -- [Ahoi2009]checker -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1802: [Ahoi2009]checker</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>75&nbsp;&nbsp;<span class=green>Solved: </span>35<br>[<a href='submitpage.php?id=1802'>Submit</a>][<a href='problemstatus.php?id=1802'>Status</a>][<a href='bbs.php?id=1802'>Discuss</a>]</center><h2>Description</h2><div class=content>在一个1行N列（N是奇数）的棋盘上，有K个格子是红色的。这种情况下，你有一个跳棋在最左端的格子上。你的目标是将它移动到最右边的格子，在开始移动之间，你可以在棋盘的任意空位上放棋子。在游戏开始后
你只可以随时在一个红色格子上放棋子。棋子的移动规则是：每次只可以选择一个棋子，跳过与之相邻的棋子走到后面的空格上，被它跳过的棋子被吃掉，即从棋盘上移走，如相邻棋子的另一侧有棋子，则不能跳。请回答以下两个问题：
1：移动开始前至少要放多少棋子才能完成任务。
2：如果要使开始前放的棋子数要求尽量少，那么在移动过程中最少需要放多少个棋子才能完成任务。
关于规则的补充说明：
1：只能往空位上放棋子，不管是移动开始前还是移动过程中。
2：移动前棋盘最左端的那个原始棋子绝对不能被吃掉.

</div><h2>Input</h2><div class=content>第一行一个正奇数N
第二行有N个整数，如果第i个整数是非功过，说明第i个格子是红棋，否则为白棋，数字间用空格分开.
</div><h2>Output</h2><div class=content>两个数字分别代表第一问和第二问的结果.
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5<br />
0 0 0 1 0<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>1 <br />
1<br />
</span></div><h2>HINT</h2>
			<div class=content><p>在游戏开始前，可以在第二个格子上放上一个棋子，游戏开始后可用最左边的棋子吃掉它，从而移动到第三格。然后由于第四格是个红色的格子，在游戏中可以在那放一个棋子，然后用已经移动第三格的棋子把它吃掉，从而达到终点。<br />
<br />
100%的数据中，N< = 1000,输出中的数字不超过10^ 15<br />
30%的数据中,N< = 20</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Day2'>Day2</a></p></div><center>[<a href='submitpage.php?id=1802'>Submit</a>][<a href='problemstatus.php?id=1802'>Status</a>][<a href='bbs.php?id=1802'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
